//
// Created by ASUS on 2024/11/24/星期日.
//
#include <bits/stdc++.h>
using namespace std;

class Block{
public:
	int t;
	vector<int> L,R,pos,sum,a,add;
	Block(vector<int>&a){//a从1开始
		this->a=a;
		int n=a.size()-1;
		pos.resize(n+1);
		add.resize(n+1);

		t=sqrt(n);
		L.resize(t+1);
		R.resize(t+1);
		sum.resize(t+1);
		for(int i=1;i<=t;i++){
			L[i]=(i-1)*t+1;
			R[i]=i*t;
		}
		if(R[t]<n){
			t++;
			L[t]=R[t-1]+1;
			R[t]=n;
		}
		for(int i=1;i<=t;i++){
			for(int j=L[i];j<=R[i];j++){
				pos[j]=i;
				sum[i]+=a[j];
			}
		}
	}

	void update(int l,int r,int x){
		int p=pos[l],q=pos[r];
		if(p==q){
			for(int i=l;i<=r;i++){
				a[i]+=x;
			}
		}else{
			for(int i=p+1;i<=q-1;i++){
				add[i]+=x;
			}
			for(int i=l;i<=R[p];i++){
				a[i]+=x;
			}
			sum[p]+=x*(R[p]-l+1);
			for(int i=L[q];i<=r;i++){
				a[i]+=x;
			}
			sum[q]+=x*(r-L[q]+1);
		}
	}

	int query(int l,int r){
		int p=pos[l],q=pos[r];
		int ans=0;
		if(p==q){
			for(int i=l;i<=r;i++){
				ans+=a[i];
			}
			ans+=add[p]*(r-l+1);
		}else{
			for(int i=p+1;i<=q-1;i++){
				ans+=sum[i]+add[i]*(R[i]-L[i]+1);
			}
			for(int i=l;i<=R[p];i++){
				ans+=a[i];
			}
			ans+=add[p]*(R[p]-l+1);
			for(int i=L[q];i<=r;i++){
				ans+=a[i];
			}
			ans+=add[q]*(r-L[q]+1);
		}
		return ans;
	}
};